package leetcode.code542.Matrix01;

/**
 * dp
 *
 * @author Max
 * @date 2021年8月20日
 * @description
 */
public class Solution54203 extends Matrix01 {

	/**
	 * m == mat.length n == mat[i].length 1 <= m, n <= 104 1 <= m * n <= 104
	 * mat[i][j] is either 0 or 1. mat 中至少有一个 0 
	 */
	@Override
	public int[][] updateMatrix(int[][] mat) {
		int h = mat.length;
		int w = mat[0].length;
		int range = h + w - 2;
		int[][] res = new int[h][w];
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (mat[i][j] == 0)
					res[i][j] = 0;
				else
					res[i][j] = range;
			}
		}
		// 向右下整理答案，取决于左边和上边，左上角的答案由下一个循环整理
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (i - 1 >= 0)
					res[i][j] = Math.min(res[i][j], res[i - 1][j] + 1);
				if (j - 1 >= 0)
					res[i][j] = Math.min(res[i][j], res[i][j - 1] + 1);
			}
		}
//		System.out.println("向下扫，向右扫");
//		for (int i = 0; i < res.length; i++) {
//			for (int j = 0; j < res[i].length; j++) {
//				System.out.print(res[i][j] + ",");
//			}
//			System.out.println("");
//		}
//		System.out.println("---");
		// 向左上整理答案，取决于右边和下边，最小值+1
		for (int i = h - 1; i >= 0; i--) {
			for (int j = w - 1; j >= 0; j--) {
				if (i + 1 < h)
					res[i][j] = Math.min(res[i][j], res[i + 1][j] + 1);
				if (j + 1 < w)
					res[i][j] = Math.min(res[i][j], res[i][j + 1] + 1);
			}
		}
		return res;
	}

	public static void main(String[] args) {
		Solution54203 so = new Solution54203();
//		so.debug1();
//		so.debug2();
//		so.debug3();
		so.debug4();
	}

}
